Hello大家好，这里是无糖的Mocha，这一期为大家介绍第二章剩下的部分内容，谓词演算的等价蕴含关系、前束范式以及谓词命题的推理理论。第二章结束之后就要开始第三章的集合论咯。

Section4.谓词演算的等价与蕴含

        与命题公式一样，谓词公式之间也具有等价关系与蕴含关系，这一部分呢，我们先来介绍几个基本概念，然后再具体地分几个部分来具体地阐述等价蕴含式。

        定义2.4.1 给定谓词公式A，如果不论对其作任何赋值，都使得谓词公式A的真值为真，则称A为永真式

        如：谓词公式A：P(x)∨¬P(x)是永真式

        定义2.4.2 给定谓词公式A、B，如果A↔B是永真式，则称A与B等价，记作A⇔B

        这等价于说，如果不论对A、B作任何同样的赋值，A与B的真值都相等，则A与B等价

        如：谓词公式A：P(x)→Q(x)⇔¬P(x)∨Q(x)

        定义2.4.3 给定谓词公式A、B，如果A→B为永真式，则称A永真蕴含B，记作A⇒B

        如：谓词公式A：P(x)∧Q(x)⇒P(x)

        介绍了上述概念，我们来分几点介绍常见的谓词演算等价与蕴含式。

（1）有限个体域下谓词演算的量词消去

        如果谓词公式的论域是有限的，那么我们可以根据量词的特点，将谓词公式化等价转换为在论域条件约束下的命题公式。

        具体地来说：

        设有限个体域上的客体变元为：a1，a2，…，an，那么

        （∀x）P（x）⇔P（a1）∧P（a2）∧…∧P（an）

        （∃x）Q（x）⇔Q（a1）∨Q（a2）∨…∨Q（an）

        用自然语言来理解，如果一个谓词公式对于论域中的任意客体均成立的话，那么对于每一个客体来说，都要满足一个命题公式成立，也就是命题公式的合取；如果一个谓词公式对于该论域，存在一个客体使之成立，那么只要所有客体满足的命题公式中，至少一个成立即可，也就是命题公式的析取。

        如：P（x）表示x是奇数，论域为{1，2，3，4，5}

        则（∃x）P（x）⇔P（1）∨P（2）∨P（3）∨P（4）∨P（5）⇔T

（2）量词的转换律

        对于这样一个命题“所有的奇数都是整数”，我们考虑其否定形式，直接否定可以得到“并非所有的奇数都是整数”，如果换一个角度来表述则有“存在一个奇数不是整数”。由此我们大致可以从中认识到否定与量词的关系，也就是量词的转换律，下面给出该公式：

        ¬（∀x）P（x）⇔（∃x）¬P（x）

        ¬（∃x）P（x）⇔（∀x）¬P（x）

        需要注意的是出现在量词前的否定，是否定的整个谓词公式。如果将其限定在有限个体域上，用德摩根律也不难证明。

        该转换律用自然语言来描述，即“并不是所有的x都有性质P”与“存在x没有性质P”是一个意思；“不存在有性质P的x”与“所有x都没有性质P”是一个意思。

        如：P（x）表示x是男生，论域：一个班的同学

        ¬（∀x）P（x）表示“并不是班级里的每个同学都是男生”

        （∃x）¬P（x）表示“存在班级里的同学，这位同学不是男生”

        根据我们的自然思维习惯，我们可以知道这两句表述是等价的，这也就是量词的转化律。

（3）量词作用域的扩充与收缩

        当一个量词的作用域中存在不受该量词约束的命题时，我们可以得到量词作用域的扩充与收缩公式，也就是量词与合取、析取的关系之一，从而将该不受约束的命题移至量词作用域之外。公式如下：

        （∀x）（P（x）∨Q）⇔（∀x）P（x）∨Q

        （∀x）（P（x）∧Q）⇔（∀x）P（x）∧Q

        （∃x）（P（x）∨Q）⇔（∃x）P（x）∨Q

        （∃x）（P（x）∧Q）⇔（∃x）P（x）∧Q

        通过上述式子我们可以通过等价定律推得如下几个公式：

        （∀x）P（x）→Q⇔（∃x）（P（x）→Q）

        （∃x）P（x）→Q⇔（∀x）（P（x）→Q）

        Q→（∀x）P（x）⇔（∀x）（Q→P（x））

        Q→（∃x）P（x）⇔（∃x）（Q→P（x））

        值得注意的是，当某些谓词的变元与量词的指导变元不相关时，也可以使用上述公式。

（4）量词的分配公式

        当量词的作用域中的命题均受该量词约束时，我们可以得到量词的分配公式，即量词与合取、析取的关系之二，从而将量词分别移至每个命题之前。

        公式如下：

        （∀x）（P（x）∧Q（x））⇔（∀x）P（x）∧（∀x）Q（x）

        “任意”对于合取运算是可分配的

        （∃x）（P（x）∨Q（x））⇔（∃x）P（x）∨（∃x）Q（x）

        “存在”对于析取运算是可分配的

        但是“任意”对于析取运算、“存在”对于合取运算是不满足等价公式的分配律的。

        比如：这些学生都聪明或者这些学生都努力，可以推出这些学生都聪明或者努力。但反过来，这些学生都聪明或者努力并不一定能够推出这些学生都聪明或者这些学生都努力。

根据如上表述我们知道这是一个蕴含关系，该蕴含关系用符号语言来表述就是：

        （∀x）P（x）∨（∀x）Q（x）⇒（∀x）（P（x）∨Q（x））

上述公式可以推出有关存在量词的一个蕴含式：

        （∃x）（P（x）∧Q（x））⇒（∃x）P（x）∧（∃x）Q（x）

类似的，我们可以得到：

        （∀x）（P（x）→Q（x））⇒（∀x）P（x）→（∀x）Q（x）

        （∀x）（P（x）↔Q（x））⇒（∀x）P（x）↔（∀x）Q（x）

至此，我们又得到了一些有关命题的等价式与蕴含式，如下表总结：

Section5.前束范式与谓词演算的推理理论

        这一部分我们首先来介绍一种形式较为规范的谓词公式，称为前束范式。顾名思义，我们把谓词公式中用来约束的量词置于整个谓词公式的前部，即可化为前束范式。

        定义 2.5.1 一个公式，如果量词均在全式的开头，它们的作用域延伸到整个公式的末尾，则称该公式为前束范式。

        前束范式可记为下述形式：

        （□v1）（□v2）…（□vn）A，其中□为量词，vi是客体变元，A是没有量词的谓词公式。

        例如：（∀x）（∃y）（P（x）→Q（y））是一个前束范式

        定理 2.5.1 任意一个谓词公式，均与一个前束范式等价。

        我们将一个谓词公式化为前束范式的过程实质上就是对于这个定理的证明。

具体步骤：

（1）首先使用等价公式，将谓词公式中的联结词均化为合取析取以及否定

（2）使用量词转化公式，将否定移至每一个命题变元和谓词填式之前

（3）利用量词关于合取与析取的分配律把量词移到全式的最前面，而后得到前束范式。

        接下来通过一个例子来说明得到前束范式的过程

例：（∃x）（¬（（∃y）P（x，y））→（（∃z）Q（z）→R（x）））

Step1 联结词转换 ⇔（∃x）（（（∃y）P（x，y））∨（¬（∃z）Q（z）∨R（x）））

Step2 否定后移 ⇔（∃x）（（（∃y）P（x，y））∨（（∀z）¬Q（z）∨R（x）））

Step3 量词前移 ⇔（∃x）（∃y）（∀z）（P（x，y）∨¬Q（z）∨R（x））

由此得到前束范式

        对于上述得到的前束范式（□v1）（□v2）…（□vn）A，若谓词公式A是合取范式，则称该前束范式为前束合取范式；若谓词公式A是析取范式，则称该前束范式为前束析取范式。

        将一个前束范式化为前束合取范式或者前束析取范式，只需将谓词公式A按照前一章之中所介绍合取范式以及析取范式的转换方法即可。

接下来介绍谓词演算的推理理论。

        与命题演算的推理理论相似，对于谓词公式来讲也有相应的推理理论，该部分的推理理论主要侧重于量词角度，量词之外的部分均与命题演算的推理理论类似。

        对于量词来说主要有四条推理规则：

        （1）全称指定规则，表示为US

        如果有（∀x）P（x）成立，那么对论域中的任意客体c，有P（c）成立

        即（∀x）P（x）⇒P（c），c为任意客体

        （2）全称推广规则，表示为UG

        如果有P（x）对论域中任意客体x成立，则有（∀x）P（x）成立

        即x为任意客体，P（x）⇒（∀x）P（x）

        （3）存在指定规则，表示为ES

        如果有（∃x）P（x）成立，那么对论域中的某些客体c，有P（c）成立

        即（∃x）P（x）⇒P（c），c为某些客体（在一些背景下也可指定为某一个客体）

        （4）存在推广规则，表示为EG

        如果有P（c）对论域中的某个客体c成立，则有（∃x）P（x）成立

        即c为某个客体，P（c）⇒（∃x）P（x）

        关于上述四条推理理论，有一些需要注意的地方：

        1.US规则中得到的P（c），以及UG规则中的P（x），这里c与x一定要是论域中的任意客体

        2.一般推理证明过程中，通常先使用ES规则，即通过存在性量词确定某一个客体，再根据US规则，也就是全称量词确定该客体所具有的性质。比如：已知（∀x）P（x）以及（∃x）（P（x）→Q（x））我们可以先通过存在量词，确定某个客体c，使得P（c）→Q（c），再根据全称量词得出P（c）成立，以此推导出Q（c）成立

        呼，这一部分的笔记其实是明天离散数学期中考试前的完成稿，整理的一个过程也相当于是自己重新复习了一遍吧，如果这一篇笔记也对你有所帮助的话可以点个赞点个关注哦！